#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;


// version 1
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0, ret = 0;
        unordered_map<int, int> hash;
        hash[0] = 1;

        //这里要做的就是，每次遍历nums中的一个数
        //每次进入循环，哈希表中总是存在区间[0 ~ i-1]的前缀和！
        for(auto x : nums){
            //计算当前位置的前缀和
            sum += x;

            int target = sum - k;
            if(hash.count(target)) ret += hash[target];

            hash[sum]++;
        }

        return ret;
    }
};